0165. 比较版本号【中等】
1. 📝 题目描述
给你两个 版本号字符串 version1 和 version2,请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。
比较版本号时,请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少,则将缺失的修订号视为 0。
返回规则如下:
- 如果
*version1* < *version2*返回-1, - 如果
*version1* > *version2*返回1, - 除此之外返回
0。
示例 1:
txt
输入:version1 = "1.2", version2 = "1.10"
输出:-1
解释:
version1 的第二个修订号为 "2"
version2 的第二个修订号为 "10":2 < 10
所以 version1 < version21
2
3
4
5
6
7
2
3
4
5
6
7
示例 2:
txt
输入:version1 = "1.01", version2 = "1.001"
输出:0
解释:
忽略前导零,"01" 和 "001" 都代表相同的整数 "1"。1
2
3
4
5
2
3
4
5
示例 3:
txt
输入:version1 = "1.0", version2 = "1.0.0.0"
输出:0
解释:
version1 有更少的修订号,每个缺失的修订号按 "0" 处理。1
2
3
4
5
2
3
4
5
提示:
1 <= version1.length, version2.length <= 500version1和version2仅包含数字和'.'version1和version2都是 有效版本号version1和version2的所有修订号都可以存储在 32 位整数 中
2. 🎯 s.1 - 双指针
c
int compareVersion(char* version1, char* version2) {
int i = 0, j = 0;
int len1 = strlen(version1), len2 = strlen(version2);
while (i < len1 || j < len2) {
int n1 = 0, n2 = 0;
while (i < len1 && version1[i] != '.') {
n1 = n1 * 10 + (version1[i] - '0');
i++;
}
while (j < len2 && version2[j] != '.') {
n2 = n2 * 10 + (version2[j] - '0');
j++;
}
if (n1 > n2) return 1;
if (n1 < n2) return -1;
i++;
j++;
}
return 0;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
js
/**
* @param {string} version1
* @param {string} version2
* @return {number}
*/
var compareVersion = function (version1, version2) {
const v1 = version1.split('.')
const v2 = version2.split('.')
const len = Math.max(v1.length, v2.length)
for (let i = 0; i < len; i++) {
const n1 = i < v1.length ? parseInt(v1[i]) : 0
const n2 = i < v2.length ? parseInt(v2[i]) : 0
if (n1 > n2) return 1
if (n1 < n2) return -1
}
return 0
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
py
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
v1 = version1.split('.')
v2 = version2.split('.')
for i in range(max(len(v1), len(v2))):
n1 = int(v1[i]) if i < len(v1) else 0
n2 = int(v2[i]) if i < len(v2) else 0
if n1 > n2:
return 1
if n1 < n2:
return -1
return 01
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
- 时间复杂度:
,其中 和 分别是两个版本号的长度 - 空间复杂度:
,分割后的数组(C 版本为 )
算法思路:
- 按
.分割版本号,逐段比较对应的修订号 - 较短的版本号缺失的段视为 0